﻿#define _CRT_SECURE_NO_WARNINGS 1

//动态规划第三题
//03_斐波那契数列模型_最小花费爬楼梯_C++
//https://leetcode.cn/problems/min-cost-climbing-stairs/description/

//没优化的代码
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 状态表示
        // dp[i] 应该表示爬上第i层台阶所花费的最小费用
        // 状态转移方程
        // dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

        // 因为要返回楼梯顶部的最低花费，所以cost.size很关键。
        // 处理边界情况
        if (cost.size() == 1)
            return cost[0];
        if (cost.size() == 2)
            return min(cost[0], cost[1]);

        vector<int> dp(cost.size() + 1);
        // 初始化
        // 下标为0或者1的台阶无需付费
        dp[0] = 0;
        dp[1] = 0;

        // 填表
        // 从下标2的台阶开始需要付费
        // 楼梯顶部的位置是cost.size()处
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[cost.size()];
    }
};

//空间优化后的代码
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //空间优化

        // 处理边界情况
        if (cost.size() == 1)
            return cost[0];
        if (cost.size() == 2)
            return min(cost[0], cost[1]);

        // 下标为0或者1的台阶无需付费
        int a = 0, b = 0, c = 0;

        // 从下标2的台阶开始需要付费
        // 楼梯顶部的位置是cost.size()处
        for (int i = 2; i <= cost.size(); i++) {
            c = min(b + cost[i - 1], a + cost[i - 2]);
            a = b;
            b = c;
        }

        return c;
    }
};